#include "mapbuilder.h"
#include "map.h"
#include "random.h"

const uint MapBuilder::BORDER = 8;

RoomBuilder::RoomBuilder()
: _targetMap( 0 )
{
}

void RoomBuilder::SetBuildTarget( Map* map, const Room& area )
{
    _targetMap = map;
    _targetRoom = area;
}

void RoomBuilder::BuildRoom()
{
    if ( !_targetMap )
        throw std::runtime_error( "Building room on invalid map" );
    BuildInternal( _targetRoom.right  - _targetRoom.left,
                   _targetRoom.bottom - _targetRoom.top );
}

uint RoomBuilder::GetTile( int x, int y ) const
{
    return _targetMap->GetTile( x + _targetRoom.left, y + _targetRoom.top ).GetType();
}

void RoomBuilder::SetTile( int x, int y, uint type )
{
    if ( x < 0 || y < 0 || x >= _targetRoom.right - _targetRoom.left ||
                           y >= _targetRoom.bottom - _targetRoom.top )
        throw std::runtime_error( "Room builder setting invalid tile" );

    _targetMap->GetTile( x + _targetRoom.left, y + _targetRoom.top ).SetType( type );
}

Map* MapBuilder::BuildMap( Game& game, uint tiles, double deadEndRetryChance )
{
    BuilderList builders;
    RoomList rooms;
    
    uint tileCount = 0;
    while ( tileCount < tiles ) {
        // Generate a roombuilder
        RoomBuilder* builder = _roomBuilderGenerator.Generate();
        builders.push_back( builder );

        // Query it for a room size
        int width;
        int height;
        builder->GetRoomSize( width, height );
        if ( width == 0 || height == 0 )
            throw std::runtime_error( "Room generated of invalid size" );

        // First room - just stick it in
        if ( !tileCount ) {
            rooms.push_back( Room( 0, width, 0, height ) );
            tileCount += uint( width ) * uint( height );
            continue;
        }
        tileCount += uint( width ) * uint( height );


        // Subsequent room - find somewhere to put it
        RoomList temp = rooms;
        bool     b = false;
        while ( !b ) {
            if ( temp.empty() )
                break;

            // Get an existing room to expand from - weighted more
            // towards bigger rooms
            int n = 0;
            foreach ( const Room& r, temp )
                n += r.right - r.left + r.bottom - r.top;
            int r = Random::Int( n );
            n = 0;
            Room base;
            for ( uint i = 0; i < temp.size(); i++ ) {
                n += temp[ i ].right - temp[ i ].left + temp[ i ].bottom - temp[ i ].top;
                if ( r < n ) {
                    base = temp[ i ];
                    temp.erase( temp.begin() + i );
                    break;
                }
            }

            std::vector< int > sides;
            sides.push_back( 0 );
            sides.push_back( 1 );
            sides.push_back( 2 );
            sides.push_back( 3 );
            while ( !sides.empty() ) {
                // Get a random side
                int r = Random::Int( sides.size() );
                int side = sides[ r ];
                sides.erase( sides.begin() + r );

                // Create an expansion room and align it
                // to the edge of the base room
                Room expand;
                if ( side == 0 ) {
                    expand.left   = base.right;
                    expand.right  = base.right + width;
                }
                if ( side == 1 ) {
                    expand.right  = base.left;
                    expand.left   = base.left - width;
                }
                if ( side == 2 ) {
                    expand.top    = base.bottom;
                    expand.bottom = base.bottom + height;
                }
                if ( side == 3 ) {
                    expand.bottom = base.top;
                    expand.top    = base.top - height;
                }

                // Calculate the points along this edge we can try
                bool tryVertical  = side < 2;
                int tries = 0;
                if ( tryVertical )
                    tries = base.bottom - base.top + height - 1;
                else
                    tries = base.right - base.left + width - 1;
                
                std::vector< int > tryPositions;
                for ( int i = 0; i < tries; i++ )
                    tryPositions.push_back( tryVertical ? base.top - height + 1 + i
                                                        : base.left - width + 1 + i );

                // Try these points
                while ( !tryPositions.empty() ) {
                    int r = Random::Int( tryPositions.size() );
                    int pos = tryPositions[ r ];
                    tryPositions.erase( tryPositions.begin() + r );

                    if ( tryVertical ) {
                        expand.top    = pos;
                        expand.bottom = pos + height;
                    }
                    else {
                        expand.left   = pos;
                        expand.right  = pos + width;
                    }

                    // If this position is valid, place the room
                    if ( IsRoomOkay( expand, rooms ) ) {
                        rooms.push_back( expand );
                        b = true;
                        break;
                    }
                }

                if ( b )
                    break;

            }
        }

        // Can't find anywhere to put it - just ignore this one
        // Shouldn't actually happen but just in case
        if ( !b ) {
            builders.erase( builders.end() - 1 );
            tileCount -= uint( width ) * uint( height );
        }

        // Prune dead ends
        if ( tileCount >= tiles ) {
            for ( uint i = 0; i < rooms.size(); i++ ) {
                int n = 0;
                if ( double( Random::Int( 100 ) ) >= deadEndRetryChance * 100.0 )
                    continue;
                for ( uint j = 0; j < rooms.size(); j++ ) {
                    if ( i == j )
                        continue;
                    if ( rooms[ i ].bottom > rooms[ j ].top && rooms[ i ].top < rooms[ j ].bottom &&
                         ( rooms[ i ].right == rooms[ j ].left || rooms[ j ].right == rooms[ i ].left ) )
                        n++;
                    else if ( rooms[ i ].right > rooms[ j ].left && rooms[ i ].left < rooms[ j ].right && 
                              ( rooms[ i ].bottom == rooms[ j ].top || rooms[ j ].bottom == rooms[ i ].top ) )
                        n++;
                }
                if ( n < 2 ) {
                    tileCount -= ( rooms[ i ].right - rooms[ i ].left ) * ( rooms[ i ].bottom - rooms[ i ].top );
                    rooms.erase( rooms.begin() + i );
                    builders.erase( builders.begin() + i );
                    i--;
                }
            }
        }
    }

    // Rooms placed, normalise map
    int left = 0, top = 0;
    foreach ( const Room& r, rooms ) {
        left = std::min( r.left, left );
        top  = std::min( r.top,  top );
    }
    foreach ( Room& r, rooms ) {
        r.left   -= left - int( BORDER );
        r.right  -= left - int( BORDER );
        r.top    -= top - int( BORDER );
        r.bottom -= top - int( BORDER );
    }
    int width = 0, height = 0;
    foreach ( const Room& r, rooms ) {
        width  = std::max( r.right + int( BORDER ),  width );
        height = std::max( r.bottom + int( BORDER ), height );
    }

    // Create map of required size and let the room builders
    // do their thing
    Map* map = new Map( game, width, height );
    for ( uint i = 0; i < builders.size(); i++ ) {
        builders[ i ]->SetBuildTarget( map, rooms[ i ] );
        builders[ i ]->BuildRoom();
    }

    // Dig corridors between rooms of common edge
    for ( uint i = 0; i < rooms.size(); i++ ) {
        for ( uint j = i + 1; j < rooms.size(); j++ ) {
            // Find common edges and dig corridors
            if ( rooms[ i ].bottom > rooms[ j ].top &&
                 rooms[ i ].top < rooms[ j ].bottom ) {
                if ( rooms[ i ].right == rooms[ j ].left )
                    DigCorridor( map, rooms[ i ], rooms[ j ], false );
                if ( rooms[ j ].right == rooms[ i ].left )
                    DigCorridor( map, rooms[ j ], rooms[ i ], false );
            }
            if ( rooms[ i ].right > rooms[ j ].left &&
                 rooms[ i ].left < rooms[ j ].right ) {
                if ( rooms[ i ].bottom == rooms[ j ].top )
                    DigCorridor( map, rooms[ i ], rooms[ j ], true );
                if ( rooms[ j ].bottom == rooms[ i ].top )
                    DigCorridor( map, rooms[ j ], rooms[ i ], true );
            }
        }
    }
    return map;
}

bool MapBuilder::IsRoomOkay( const Room& room, const RoomList& otherRooms )
{
    foreach ( const Room& r, otherRooms ) {
        if ( r.left < room.right && r.right > room.left &&
             r.top < room.bottom && r.bottom > room.top )
             return false;
    }
    return true;
}

void MapBuilder::DigCorridor( Map* map, const Room& first, const Room& second, bool vertical )
{
    // Find the common section of edge
    int low  = std::max( vertical ? first.left  : first.top,    vertical ? second.left  : second.top );
    int high = std::min( vertical ? first.right : first.bottom, vertical ? second.right : second.bottom );

    // Find the closest rows/columns
    bool b = false;
    int start, end;
    while ( !b ) {
        b = true;

        start = 0;
        for ( int x = ( vertical ? low : first.left ); x < ( vertical ? high : first.right ); x++ ) {
            for ( int y = ( vertical ? first.top : low ); y < ( vertical ? first.bottom : high ); y++ ) {
                if ( !map->GetTile( x, y ).IsBlocked() )
                    start = std::max( start, vertical ? y : x );
            }
        }
        end = vertical ? second.bottom : second.right;
        for ( int x = ( vertical ? low : second.left ); x < ( vertical ? high : second.right ); x++ ) {
            for ( int y = ( vertical ? second.top : low ); y < ( vertical ? second.bottom : high ); y++ ) {
                if ( !map->GetTile( x, y ).IsBlocked() )
                    end = std::min( end, vertical ? y : x );
            }
        }

        // Couldn't find anywhere between two rooms sharing all of a common edge -
        // must be a recursion into the wrong part, just skip
        if ( ( start == 0 || end == ( vertical ? second.bottom : second.right ) ) &&
             ( ( vertical && first.left == second.left && first.right == second.right ) ||
               ( !vertical && first.top == second.top && first.bottom == second.bottom ) ) )
               return;

        // We couldn't find anywhere - dig recursively
        if ( start == 0 ) {
            b = false;
            Room fnew = first;
            Room snew = first;
            map->GetTile( vertical ? ( low + high ) / 2 : ( first.left + first.right ) / 2,
                          vertical ? ( first.top + first.bottom ) / 2 : ( low + high ) / 2 ).SetType( Tile::FLOOR );

            if ( vertical )
                fnew.right = snew.left = low;
            else
                fnew.bottom = snew.top = low;
            if ( fnew.bottom > fnew.top && fnew.right > fnew.left &&
                 snew.bottom > snew.top && snew.right > snew.left )
                DigCorridor( map, fnew, snew, !vertical );

            if ( vertical )
                fnew.right = snew.left = high;
            else
                fnew.bottom = snew.top = high;
            if ( fnew.bottom > fnew.top && fnew.right > fnew.left &&
                 snew.bottom > snew.top && snew.right > snew.left )
                DigCorridor( map, fnew, snew, !vertical );
        }
        if ( end == ( vertical ? second.bottom : second.right ) ) {
            b = false;
            Room fnew = second;
            Room snew = second;
            map->GetTile( vertical ? ( low + high ) / 2 : ( second.left + second.right ) / 2,
                          vertical ? ( second.top + second.bottom ) / 2 : ( low + high ) / 2 ).SetType( Tile::FLOOR );

            if ( vertical )
                fnew.right = snew.left = low;
            else
                fnew.bottom = snew.top = low;
            if ( fnew.bottom > fnew.top && fnew.right > fnew.left &&
                 snew.bottom > snew.top && snew.right > snew.left )
                DigCorridor( map, fnew, snew, !vertical );

            if ( vertical )
                fnew.right = snew.left = high;
            else
                fnew.bottom = snew.top = high;
            if ( fnew.bottom > fnew.top && fnew.right > fnew.left &&
                 snew.bottom > snew.top && snew.right > snew.left )
                DigCorridor( map, fnew, snew, !vertical );
        }
    }

    // Find the maximum corridor size
    int n = 0;
    int firstMax = 0;
    for ( int i = low; i < high; i++ ) {
        if ( !map->GetTile( vertical ? i : start, vertical ? start : i ).IsBlocked() )
            n++;
        else
            n = 0;
        firstMax = std::max( firstMax, n );
    }
    n = 0;
    int secondMax = 0;
    for ( int i = low; i < high; i++ ) {
        if ( !map->GetTile( vertical ? i : end, vertical ? end : i ).IsBlocked() )
            n++;
        else
            n = 0;
        secondMax = std::max( secondMax, n );
    }
    int cMax = std::min( firstMax, secondMax );

    // Choose corridor size at random, but not bigger than the length
    int cSize = std::min( Random::Int( cMax ) + 1, end - start + 1 );

    // Find possible positions to put the ends of the corridor
    n = 0;
    std::vector< int > firstPositions;
    for ( int i = low; i < high; i++ ) {
        if ( !map->GetTile( vertical ? i : start, vertical ? start : i ).IsBlocked() )
            n++;
        else
            n = 0;
        if ( n >= cSize )
            firstPositions.push_back( i - cSize + 1 );
    }
    n = 0;
    std::vector< int > secondPositions;
    for ( int i = low; i < high; i++ ) {
        if ( !map->GetTile( vertical ? i : end, vertical ? end : i ).IsBlocked() )
            n++;
        else
            n = 0;
        if ( n >= cSize )
            secondPositions.push_back( i - cSize + 1 );
    }

    // Choose positions at random
    int r = Random::Int( firstPositions.size() );
    int firstPos = firstPositions[ r ];
    r = Random::Int( secondPositions.size() );
    int secondPos = secondPositions[ r ];
    int changePos = Random::Int( end - start - cSize + 2 ) + start;

    // Dig the corridor
    int lowBound  = std::min( firstPos, secondPos );
    int highBound = std::max( firstPos, secondPos ) + cSize - 1;
    for ( int i = start; i <= end; i++ ) {
        for ( int j = lowBound; j <= highBound; j++ ) {
            if ( ( i < changePos && j >= firstPos && j < firstPos + cSize ) ||
                 ( i >= changePos && i < changePos + cSize ) ||
                 ( i >= changePos + cSize && j >= secondPos && j < secondPos + cSize ) ) {
                map->GetTile( vertical ? j : i, vertical ? i : j ).SetType( Tile::FLOOR );
            }
        }
    }

}